package com.zecan;

import java.util.ArrayList;
import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/19
 * \* Time: 12:20
 * \* Description:
 * \
 */
public class cheesboard {
    static int cut = 0; // 标记马已经走的格子数
    static int num = 0; // 标记棋盘走满的方案的个数

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        // 棋盘移动的距离
        int move[][] = new int[][]{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
        int[][] M = new int[12][12];
        //其中i=0,1,11,12和j=0,1,11,12表示围墙，马可以踏但是不算在计数中；
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M[i].length; j++) {
                if (i == 1 || i == 0 || i == 10 || i == 11 || j == 0 || j == 1 || j == 10 || j == 11) {
                    M[i][j] = -1;
                }
            }
        }
        M[2][2] = ++cut;
        long start = System.currentTimeMillis();
        new cheesboard().Horse(2, 2, M, move);
        long end = System.currentTimeMillis();
        System.out.println( "需要的时间"  + (end - start));
    }

    /**
     * 马踏棋盘的方法
     *
     * @param x 传递过来的马从第几行开始
     * @param y 传递过来的马从第几列开始
     * @return void
     * @author
     * @creed: Talk is cheap,show me the code
     * @date 2021年10月19日18:29:57
     */
    public void Horse(int x, int y, int[][] M, int[][] move) {
        if (cut == 64) {
            num++;
            System.out.println("第" + num + "解为：");
            printChessBoard(M);
            return;
        }
        for (int i = 0; i < 8; i++) {
            int a = x + move[i][0];//计算马行向走的距离
            int b = y + move[i][1];//计算马列走的距离
            if (M[a][b] == 0) { // 如果当前位置没有被访问过
                M[a][b] = ++cut; // 如果当前位置没有被访问过,那么就将当前位置赋上其对应的步数
                Horse(a, b, M, move);// 递归从这个步开始进行下一次的走步
                cut--; // 如果回溯回来代表当前步骤无法走通
                M[a][b] = 0;
            }
        }
    }

    public void printChessBoard(int[][] M) {
        for (int i = 2; i < M.length - 2; i++) {
            for (int j = 2; j < M.length - 2; j++) {
                System.out.print(M[i][j] + " ");
            }
            System.out.println();
        }
    }
}
